#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <thread>
#include <mutex>
#include <chrono>
#include <set>
#include <cmath>
using namespace std;

// ----------------------------- 方法一的相关代码 -----------------------------
struct Path {
    vector<size_t> nodes;
    size_t length;
    bool operator>(const Path& other) const {
        return length > other.length;
    }
};

bool dfs(size_t start, size_t end, const vector<vector<size_t>>& roadlength, vector<bool>& visited, vector<size_t>& current_path, vector<vector<size_t>>& all_paths, size_t k) {
    visited[start] = true;
    current_path.push_back(start);

    if (start == end) {
        all_paths.push_back(current_path);
        if (all_paths.size() > k) {
            current_path.pop_back();
            visited[start] = false;
            return false;
        }
    } else {
        for (size_t i = 0; i < roadlength.size(); i++) {
            if (roadlength[start][i] != INT_MAX && !visited[i]) {
                if (!dfs(i, end, roadlength, visited, current_path, all_paths, k)) {
                    current_path.pop_back();
                    visited[start] = false;
                    return false;
                }
            }
        }
    }

    current_path.pop_back();
    visited[start] = false;
    return true;
}

vector<size_t> dijkstra(size_t start, size_t end, const vector<vector<size_t>>& roadlength) {
    const size_t INF = INT_MAX;
    const size_t n = roadlength.size();
    vector<size_t> dist(n, INF);
    dist[start] = 0;
    vector<size_t> prev(n, INF);

    priority_queue<pair<size_t, size_t>, vector<pair<size_t, size_t>>, greater<pair<size_t, size_t>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (u == end) break;
        if (d > dist[u]) continue;

        for (size_t v = 0; v < n; ++v) {
            if (roadlength[u][v] != INF && dist[v] > dist[u] + roadlength[u][v]) {
                dist[v] = dist[u] + roadlength[u][v];
                prev[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    if (dist[end] == INF) return {};

    vector<size_t> path;
    for (size_t cur = end; cur != start; cur = prev[cur]) {
        if (prev[cur] == INF) return {};
        path.push_back(cur);
    }
    path.push_back(start);

    reverse(path.begin(), path.end());
    return path;
}

size_t calculatePathLength(const vector<size_t>& path, const vector<vector<size_t>>& roadlength) {
    size_t length = 0;
    for (size_t i = 0; i < path.size() - 1; ++i) {
        length += roadlength[path[i]][path[i + 1]];
    }
    return length;
}

vector<vector<size_t>> yen_ksp(size_t start, size_t end, size_t k, const vector<vector<size_t>>& roadlength) {
    vector<vector<size_t>> P;
    if (k == 0) return P;

    auto firstPath = dijkstra(start, end, roadlength);
    if (firstPath.empty()) return P;
    P.push_back(firstPath);

    priority_queue<Path, vector<Path>, greater<Path>> Q;
    set<vector<size_t>> usedPaths;
    usedPaths.insert(firstPath);

    for (size_t i = 0; i < firstPath.size() - 1; ++i) {
        size_t r = firstPath[i];
        size_t s = firstPath[i + 1];

        vector<vector<size_t>> modified_roadlength = roadlength;
        modified_roadlength[r][s] = INT_MAX;
        modified_roadlength[s][r] = INT_MAX;

        auto spurPath = dijkstra(r, end, modified_roadlength);
        if (!spurPath.empty()) {
            vector<size_t> newPath(firstPath.begin(), firstPath.begin() + i + 1);
            newPath.insert(newPath.end(), spurPath.begin() + 1, spurPath.end());

            size_t newLen = calculatePathLength(newPath, roadlength);

            if (!usedPaths.count(newPath)) {
                usedPaths.insert(newPath);
                Q.push({newPath, newLen});
            }
        }
    }

    while (!Q.empty() && P.size() < k) {
        Path candidate = Q.top();
        Q.pop();

        bool duplicate = false;
        for (auto &p : P) {
            if (p == candidate.nodes) {
                duplicate = true;
                break;
            }
        }
        if (duplicate) continue;

        P.push_back(candidate.nodes);

        for (size_t i = 0; i < candidate.nodes.size() - 1; ++i) {
            size_t r = candidate.nodes[i];
            size_t s = candidate.nodes[i + 1];

            vector<vector<size_t>> modified_roadlength = roadlength;
            modified_roadlength[r][s] = INT_MAX;
            modified_roadlength[s][r] = INT_MAX;

            auto spurPath = dijkstra(r, end, modified_roadlength);
            if (!spurPath.empty()) {
                vector<size_t> newPath(candidate.nodes.begin(), candidate.nodes.begin() + i + 1);
                newPath.insert(newPath.end(), spurPath.begin() + 1, spurPath.end());

                size_t newLen = calculatePathLength(newPath, roadlength);

                if (!usedPaths.count(newPath)) {
                    usedPaths.insert(newPath);
                    Q.push({newPath, newLen});
                }
            }
        }
    }

    return P;
}
struct Event1 {
    size_t time;
    size_t u; // 起始节点
    size_t v; // 结束节点
    bool enter; // 进入路段（true）还是离开路段（false）
    // 重载比较运算符，使优先队列按时间升序排列
    bool operator>(const Event1& other) const {
        return time > other.time;
    }
};
bool checkTraffic(const vector<vector<size_t>>& combination,
                  const vector<vector<size_t>>& roadlength,
                  const vector<vector<size_t>>& restrictions) {
    priority_queue<Event1, vector<Event1>, greater<Event1>> eventQueue;

    for (const auto& path : combination) {
        size_t current_time = 0;
        for (size_t i = 1; i < path.size(); ++i) {
            size_t u = path[i - 1];
            size_t v = path[i];
            size_t length = roadlength[u][v];

            eventQueue.push({current_time, u, v, true});
            eventQueue.push({current_time + length, u, v, false});

            current_time += length;
        }
    }

    vector<vector<size_t>> current_flow(roadlength.size(), vector<size_t>(roadlength.size(), 0));

    while (!eventQueue.empty()) {
        size_t current_time = eventQueue.top().time;

        vector<Event1> sameTimeEvents;
        while (!eventQueue.empty() && eventQueue.top().time == current_time) {
            sameTimeEvents.push_back(eventQueue.top());
            eventQueue.pop();
        }

        for (auto &event : sameTimeEvents) {
            if (!event.enter) {
                if (current_flow[event.u][event.v] > 0) {
                    current_flow[event.u][event.v]--;
                    current_flow[event.v][event.u]--;
                }
            }
        }

        for (auto &event : sameTimeEvents) {
            if (event.enter) {
                current_flow[event.u][event.v]++;
                current_flow[event.v][event.u]++;
                if (current_flow[event.u][event.v] > restrictions[event.u][event.v]) {
                    return false;
                }
            }
        }
    }

    return true;
}

size_t calculateTotalLength(const vector<vector<size_t>>& combination, const vector<vector<size_t>>& roadlength) {
    size_t total_length = 0;
    for (const vector<size_t>& path : combination) {
        for (size_t i = 1; i < path.size(); i++) {
            size_t u = path[i - 1];
            size_t v = path[i];
            total_length += roadlength[u][v];
        }
    }
    return total_length;
}

int traverseCombinations(const vector<vector<vector<size_t>>>& all_cars_paths,
                          size_t car_index,
                          vector<vector<size_t>>& current_combination,
                          const vector<vector<size_t>>& roadlength,
                          const vector<vector<size_t>>& restrictions,
                          vector<vector<size_t>>& best_combination,
                          size_t& min_total_length) {
    static auto start_time = chrono::high_resolution_clock::now();
    if (car_index == all_cars_paths.size()) {
        if (checkTraffic(current_combination, roadlength, restrictions)) {
            size_t total_length = calculateTotalLength(current_combination, roadlength);
            if (total_length < min_total_length) {
                min_total_length = total_length;
                best_combination = current_combination;
            }
        }
        auto current_time = chrono::high_resolution_clock::now();
        auto elapsed_time = chrono::duration_cast<chrono::milliseconds>(current_time - start_time).count();
        if (elapsed_time >= 19500) {
            return 1;
        }
        return 0;
    }

    for (const auto &path : all_cars_paths[car_index]) {
        current_combination.push_back(path);
        if(traverseCombinations(all_cars_paths, car_index + 1, current_combination,
                             roadlength, restrictions, best_combination,
                             min_total_length)){
            return 1;
        }
        current_combination.pop_back();
    }
    return 0;
}

int findBestCombination(const vector<vector<vector<size_t>>>& all_cars_paths,
                         const vector<vector<size_t>>& roadlength,
                         const vector<vector<size_t>>& restrictions,
                         vector<vector<size_t>>& best_combination,
                         size_t& min_total_length) {
    best_combination.clear();
    min_total_length = SIZE_MAX;

    vector<vector<size_t>> current_combination;
    return traverseCombinations(all_cars_paths, 0, current_combination,
                         roadlength, restrictions, best_combination,
                         min_total_length);
}

//使用dijkstra算法+优先队列的方法
struct Event {
    int time;
    int car_id;
    int from;
    int to;
    Event(int time, int id, int a, int b) : time(time), car_id(id), from(a), to(b) {}
    bool operator<(const Event& next) const {
        return this->time > next.time;
    }
};

vector<int> dijkstra(int N, int start, int end, const vector<vector<int>>& roadlength, const vector<vector<int>>& flow, const vector<vector<int>>& restrictions) {
    vector<int> distance(N, INT_MAX);
    vector<int> previous(N, -1);
    vector<bool> visited(N, false);

    distance[start] = 0;

    for (int i = 0; i < N - 1; i++) {
        int min_distance = INT_MAX;
        int stop = start;

        for (int j = 0; j < N; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                stop = j;
            }
        }

        visited[stop] = true;

        for (int k = 0; k < N; k++) {
            if (!visited[k] && roadlength[stop][k] < INT_MAX && flow[stop][k] < restrictions[stop][k] && distance[stop] + roadlength[stop][k] < distance[k]) {
                distance[k] = distance[stop] + roadlength[stop][k];
                previous[k] = stop;
            }
        }
    }

    vector<int> path;
    int node = end;
    while (node != -1) {
        path.push_back(node);
        node = previous[node];
    }
    reverse(path.begin(), path.end());

    return path;
}

int mainMethod2(int N, int M, const vector<vector<int>>& roadlength,
                const vector<vector<int>>& restrictions,
                const vector<vector<int>>& cars) {
    vector<vector<int>> flow(N, vector<int>(N, 0));

    priority_queue<Event> event_queue;
    vector<vector<int>> paths(M);
    vector<vector<int>> history(M);
    vector<int> car_arrival_time(M, -1);

    for (int i = 0; i < M; i++) {
        paths[i] = dijkstra(N, cars[i][0], cars[i][1], roadlength, flow, restrictions);

        if (paths[i].size() == 1) {
            if (paths[i][0] == cars[i][0]) {
                car_arrival_time[i] = 0;
                history[i].push_back(cars[i][0]);
                history[i].push_back(cars[i][0]);
                continue;
            } else {
                history[i].push_back(cars[i][0]);
                event_queue.push(Event(1, i, cars[i][0], cars[i][0]));
                continue;
            }
        }

        history[i].push_back(cars[i][0]);
        int u = paths[i][0];
        int v = paths[i][1];
        int time = roadlength[u][v];
        event_queue.push(Event(time, i, u, v));
        flow[u][v]++;
        flow[v][u]++;

        paths[i].erase(paths[i].begin());
    }

    while (!event_queue.empty()) {
        int current_time = event_queue.top().time;

        vector<Event> current_events;
        while (!event_queue.empty() && event_queue.top().time == current_time) {
            Event event = event_queue.top();
            current_events.push_back(event);
            event_queue.pop();
            if (event.from != event.to) {
                flow[event.from][event.to]--;
                flow[event.to][event.from]--;
                history[event.car_id].push_back(event.to);
            }
        }
        for (Event event : current_events) {
            if (event.to == cars[event.car_id][1]) {
                car_arrival_time[event.car_id] = current_time;
            } else {
                vector<int> newpath = dijkstra(N, history[event.car_id].back(), cars[event.car_id][1], roadlength, flow, restrictions);
                if (newpath.size() == 1) {
                    event_queue.push(Event(current_time+1, event.car_id, event.from, event.to));
                    continue;
                } else {
                    paths[event.car_id] = newpath;
                    int u = newpath[0];
                    int v = newpath[1];
                    flow[u][v]++;
                    flow[v][u]++;
                    int travel_time = current_time + roadlength[u][v];
                    event_queue.push(Event(travel_time, event.car_id, u, v));
                }
            }
        }
    }

    int sum = 0;
    for (int i = 0; i < M; i++) {
        sum += car_arrival_time[i];
    }
    return sum;
}

// ----------------------------- 主函数和多线程逻辑 -----------------------------
mutex mtx;
vector<vector<size_t>> best_combination_method1;
size_t min_total_length_method1 = SIZE_MAX;
int sum_method2 = INT_MAX;
bool method1_timeout = false;

void runMethod1(const vector<vector<vector<size_t>>>& all_cars_paths,
                const vector<vector<size_t>>& roadlength,
                const vector<vector<size_t>>& restrictions) {
    vector<vector<size_t>> best_combination;
    size_t min_total_length;
    
    int result = findBestCombination(all_cars_paths, roadlength, restrictions, best_combination, min_total_length);
    //cout<<min_total_length<<endl;
    lock_guard<mutex> lock(mtx);
    if (result == 1) {
        method1_timeout = true;
    }
    best_combination_method1 = best_combination;
    min_total_length_method1 = min_total_length;
    
}

void runMethod2(int N, int M, const vector<vector<int>>& roadlength,
                const vector<vector<int>>& restrictions,
                const vector<vector<int>>& cars) {
    int sum = mainMethod2(N, M, roadlength, restrictions, cars);

    lock_guard<mutex> lock(mtx);
    sum_method2 = sum;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<size_t>> roadlength(N, vector<size_t>(N, INT_MAX));
    vector<vector<size_t>> restrictions(N, vector<size_t>(N, 0));
    vector<vector<size_t>> cars(M, vector<size_t>(2));

    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 0; j < N; ++j) {
            cin >> roadlength[i][j];
            if (roadlength[i][j] == 0 && i != j) {
                roadlength[i][j] = INT_MAX;
            }
        }
    }

    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 0; j < N; ++j) {
            cin >> restrictions[i][j];
        }
    }

    for (size_t i = 0; i < M; ++i) {
        cin >> cars[i][0] >> cars[i][1];
        cars[i][0]--;
        cars[i][1]--;
    }

    size_t k = (size_t)pow(INT_MAX, 1.0 / (N + M)) + 1;
    vector<vector<vector<size_t>>> all_cars_paths(M);

    for (size_t i = 0; i < M; ++i) {
        size_t start = cars[i][0];
        size_t end = cars[i][1];

        vector<bool> visited(N, false);
        vector<size_t> current_path;
        vector<vector<size_t>> all_paths;
        
        if (dfs(start, end, roadlength, visited, current_path, all_paths, k)) {
            all_cars_paths[i] = all_paths;
        } else {
            all_cars_paths[i] = yen_ksp(start, end, k, roadlength);
        }
    }

    vector<vector<int>> roadlength_int(N, vector<int>(N));
    vector<vector<int>> restrictions_int(N, vector<int>(N));
    vector<vector<int>> cars_int(M, vector<int>(2));

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            roadlength_int[i][j] = static_cast<int>(roadlength[i][j]);
            restrictions_int[i][j] = static_cast<int>(restrictions[i][j]);
        }
    }

    for (int i = 0; i < M; ++i) {
        cars_int[i][0] = static_cast<int>(cars[i][0]);
        cars_int[i][1] = static_cast<int>(cars[i][1]);
    }

    thread t1(runMethod1, all_cars_paths, roadlength, restrictions);
    thread t2(runMethod2, N, M, roadlength_int, restrictions_int, cars_int);
    
    t2.join();
    t1.join();

    lock_guard<mutex> lock(mtx);
    if (!method1_timeout) {
        cout << "Method 1 result (total length: " << min_total_length_method1 << "):\n";
        for (size_t i = 0; i < best_combination_method1.size(); i++) {
            cout << "Car " << i + 1 << " path: ";
            for (size_t node : best_combination_method1[i]) {
                cout << node + 1 << " ";
            }
            cout<<endl;
        }
    } else {
        if (min_total_length_method1 < sum_method2) {
            cout << "Method 1 result (total length: " << min_total_length_method1 << "):\n";
            for (size_t i = 0; i < best_combination_method1.size(); i++) {
                cout << "Car " << i + 1 << " path: ";
                for (size_t node : best_combination_method1[i]) {
                    cout << node + 1 << " ";
                }
                cout << "\n";
            }
        } else {
            cout << "Method 2 result (total time: " << sum_method2 << "):\n";
        }
    }

    return 0;
}